package paixu;

import java.util.Arrays;

public class MergetSort {
    public static void main(String[] args) {
        int arr[]={8,4,5,7,1,3,6,2};
        int temp [] = new int[arr.length];
        System.out.println(Arrays.toString(arr));
        merge(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }
    public static void merge(int arr[],int left,int right,int temp[]){
        if(left<right){
            int mid = (left+right)/2;
            merge(arr,left,mid,temp);
            merge(arr,mid+1,right,temp);
            sort(arr,left,right,temp,mid);
        }
    }
    public static void sort(int arr[],int left,int right,int temp[],int mid){
        int i = left;
        int j = mid+1;
        int t = 0;
        //把左右两边数组填充到arr
        while(i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t]=arr[i];
                i+=1;
                t+=1;
            }else {
                temp[t]=arr[j];
                j+=1;
                t+=1;
            }
        }

        while (i<=mid){
            temp[t]=arr[i];
            i+=1;
            t+=1;
        }
        while (j<=right){
            temp[t]=arr[j];
            j+=1;
            t+=1;
        }
        System.out.println("t+"+Arrays.toString(temp));
        //将temp赋值给arr
        int tempLeft = left;
        t=0;
        while (tempLeft<=right){
            System.out.println(tempLeft);
            arr[tempLeft]=temp[t];
            tempLeft++;
            t++;
        }
    }
}
